package com.rui.study.algorithm.P_零杠一背包PLUS_回溯解法;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-29 14:44
 **/
public class Solution {

    private int[] weight;   // 物品重量
    private int[] value;    // 物品价值

    private int w;          // 背包承重

    private int maxV;       // 最大价值

    public Solution(int[] weight, int[] value, int w) {
        this.weight = weight;
        this.value = value;
        this.w = w;
    }

    public void knapsack(int n, int cw, int cv) {
        if (cw == w || n == weight.length) {
            if (cv > maxV) maxV = cv;
            return;
        }

        knapsack(n + 1, cw, cv);        // 当前物品不放入背包

        if (cw + weight[n] <= w) {
            knapsack(n + 1, cw + weight[n], cv + value[n]); // 当前物品放入背包
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution(new int[]{2, 3, 6, 7, 9},
                new int[]{4, 3, 3, 9, 6}, 12);
        solution.knapsack(0, 0, 0);
        System.out.println("最大价值：" + solution.maxV);
    }
}
